package com.gzzz.sort;

import java.util.*;

public class BucketSortString {

    // 桶排序算法
    public static ArrayList<String> sort(ArrayList<String> list) {
        if (list == null || list.size() <= 1) {
            return null;
        }

        int n = list.size();

        // 创建一个 HashMap 用于存储桶
        Map<Character, ArrayList<String>> buckets = new HashMap<>();

        // 将字符串放入相应的桶中，按照首字母分类
        for (String str : list) {
            char firstChar = Character.toLowerCase(str.charAt(0)); // 将首字母转换为小写以进行分类
            if (!buckets.containsKey(firstChar)) {
                buckets.put(firstChar, new ArrayList<>());
            }
            buckets.get(firstChar).add(str);
        }

        // 在每个桶内部对字符串进行排序
        for (ArrayList<String> bucket : buckets.values()) {
            Collections.sort(bucket); // 使用内置的排序方法对桶内的字符串进行排序
        }

        // 将排序后的字符串放到新列表
        ArrayList<String> new_list = new ArrayList<>();
        int index = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            ArrayList<String> bucket = buckets.get(c);
            if (bucket != null) {
                new_list.addAll(bucket);
            }
        }

        // 返回排序后的列表
        return new_list;
    }

    // 示例
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("bubble");
        list.add("Abandon Baby Love Baby Abandon");
        list.add("Bbandon Baby Love Baby Abandon");
        list.add("wiki");
        list.add("Where there is a will, there is a way");
        list.add("Taokku");


        ArrayList<String> new_list = sort(list);

        System.out.println("Sorted list:");
        for (String item : new_list) {
            System.out.println(item);
        }
    }
}
